package datastruct.linkedlist;

import java.util.Optional;
import java.util.function.Consumer;

/**
 * 双链表
 */
public class DoubleLinkedList<T> {

    private Node<T> first;
    private Node<T> last;
    private int size;

    private static class Node<T> {
        T data;
        Node<T> prev;
        Node<T> next;

        Node(T data) {
            this.data = data;
        }
    }

    /**
     * 根据索引找到节点
     */
    private Node<T> find(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("索引越界");
        }
        Node<T> temp = first;
        for (int i = 0; i < index; i++) {
            temp = temp.next;
        }
        return temp;
    }

    public void add(T data) {
        Node<T> node = new Node<>(data);
        node.prev = last;
        Optional.ofNullable(last).ifPresent(n -> n.next = node);
        last = node;
        if (size == 0) {
            first = node;
        }
        size++;
    }

    public void add(int index, T data) {
        if (index == size) {
            add(data);
            return;
        }
        Node<T> temp = find(index);
        Node<T> node = new Node<>(data);
        node.prev = temp.prev;
        node.next = temp;
        if (temp.prev == null) {
            first = node;
        } else {
            temp.prev.next = node;
        }
        temp.prev = node;
        size++;
    }

    public void delete(int index) {
        Node<T> node = find(index);

        if (node.prev == null) {
            // 链头
            first = node.next;
        } else {
            node.prev.next = node.next;
            node.prev = null;
        }

        if (node.next == null) {
            // 链尾
            last = node.prev;
        } else {
            node.next.prev = node.prev;
            node.next = null;
        }
        node.data = null;
        size--;
    }

    public void update(int index, T data) {
        find(index).data = data;
    }

    public T get(int index) {
        return find(index).data;
    }

    public void forEach(Consumer<T> consumer) {
        Node<T> temp = first;
        for (int i = 0; i < size; i++) {
            consumer.accept(temp.data);
            temp = temp.next;
        }
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        forEach(data -> builder.append(data).append(", "));
        int len = builder.length();
        if (len > 2) {
            builder.delete(len - 2, len);
        }
        return builder.insert(0, "[").append("]").toString();
    }
}
